package com.lili.greedy;

import java.util.*;

/**
 * @Auther: 李 力
 * @Date: 2024/8/6
 * @Description: 无重叠区间: 本质上就是活动选择性问题
 * @version: 1.0
 */

/*
 *  要在会议室里面举办n个活动
 *  每个活动有它们各自的开始时间和结束时间
 *  找出在时间上互相不冲突的活动组合，能够最充分的利用教室
 * */
public class Leetcode435 {

    /*
     * 思路: 贪心算法,应该选择最先结束的活动
     * 时间复杂度:
     * 空间复杂度:
     * activities:活动数组
     * n:数组长度
     * */

    public static List<Activity> select(Activity[] activities, int n) {
        //结果:保存被选择的活动
        List<Activity> result = new ArrayList<>();
        //先按照结束时间升序排序
        Arrays.sort(activities, Comparator.comparingInt(Activity::getEnd));
        result.add(activities[0]);
        Activity prev = activities[0];//上次被选中的活动
        for (int i = 1; i < n; i++) {
            Activity curr = activities[i];//当前正在处理的活动
            if (curr.getStart() >= prev.getEnd()) {
                result.add(curr);
                prev = curr;
            }
        }
        return result;
    }
}
